package org.example.Sort;

import org.example.Tool.Tool;

import java.util.Arrays;

/**
 **<pre>
 * name 堆排序
 * time N(log^N)
 * space O（1）
 * @apiNote 堆实际上是一个树
 * </pre>
 * */
public class HeapSort extends Tool {
    public void sort(int arr[]){
        //去掉捣乱数组
        if(arr==null ||arr.length<2){
            return;
        }
        //维护堆结构
        for(int i=0;i<arr.length;i++){
            heapInsert(arr,i);//Olog^N
        }
        //替换最大值
        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        //重复操作
        while(heapSize>0){
            heapify(arr,0,heapSize);//Olog^N
            swap(arr,0,--heapSize);
        }
    }
    /**
     * @apiNote 上移插入
     * */
    public void heapInsert(int []arr,int index){
        while(arr[index]>arr[(index-1)/2]){
            swap(arr,index,(index-1)/2);
            index = (index-1)/2;
        }
    }
    /**@apiNote 下移插入*/
    private void heapify(int []arr,int index,int heapSize){
        int left = index*2+1;
        while(left<heapSize){
            //两个孩子之中，谁的值最大，把下标给largest
            int largest = left+1<heapSize&&arr[left+1]>arr[left]?left+1:left;
            //父和孩子之中，谁的值最大，把下标给largest
            largest = arr[largest] >arr[index]?largest:index;
            if(largest==index){
                break;
            }
            swap(arr,largest,index);
            left++;
        }
    }

    public static void main(String[] args) {
        int arr[] = {1,123,12,31,56641,132,6};
        new HeapSort().sort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }
}
